/**********************************************************************

Audacity: A Digital Audio Editor

Registry.cpp

Paul Licameli split from Menus.cpp

**********************************************************************/

#include "Registry.h"

#include <unordered_set>

#include <wx/log.h>

#include "BasicUI.h"

namespace {
struct ItemOrdering;

using namespace Registry;
using namespace detail;

//! Used only internally
struct PlaceHolder : GroupItemBase {
    PlaceHolder(const Identifier& identifier, Ordering ordering)
        : GroupItemBase{identifier}
        , ordering{ordering == Strong ? Weak : ordering}
    {}
    ~PlaceHolder() = default;
    Ordering GetOrdering() const override
    {
        return ordering;
    }

    Ordering ordering;
};

struct CollectedItems
{
    struct Item {
        // Predefined, or merged from registry already:
        BaseItem* visitNow;
        // Corresponding item from the registry, its sub-items to be merged:
        GroupItemBase* mergeLater;
        // Ordering hint for the merged item:
        OrderingHint hint;
    };
    std::vector< Item > items;
    std::vector< BaseItemSharedPtr >& computedItems;

    // A linear search.  Smarter search may not be worth the effort.
    using Iterator = decltype(items)::iterator;
    auto Find(const Identifier& name) -> Iterator
    {
        auto end = items.end();
        return name.empty()
               ? end
               : std::find_if(items.begin(), end,
                              [&]( const Item& item ){
            return name == item.visitNow->name;
        });
    }

    auto InsertNewItemUsingPreferences(
        ItemOrdering& itemOrdering, BaseItem* pItem) -> bool;

    auto InsertNewItemUsingHint(
        BaseItem* pItem, const OrderingHint& hint, size_t endItemsCount, bool force)
    -> bool;

    auto MergeLater(Item& found, const Identifier& name, GroupItemBase::Ordering ordering) -> GroupItemBase *;

    void SubordinateSingleItem(Item& found, BaseItem* pItem);

    void SubordinateMultipleItems(Item& found, GroupItemBase& items);

    bool MergeWithExistingItem(ItemOrdering& itemOrdering, BaseItem* pItem);

    using NewItem = std::pair< BaseItem*, OrderingHint >;
    using NewItems = std::vector< NewItem >;

    bool MergeLikeNamedItems(ItemOrdering& itemOrdering, NewItems::const_iterator left, NewItems::const_iterator right, int iPass,
                             size_t endItemsCount, bool force);

    void MergeItemsAscendingNamesPass(ItemOrdering& itemOrdering, NewItems& newItems, int iPass, size_t endItemsCount, bool force);

    void MergeItemsDescendingNamesPass(ItemOrdering& itemOrdering, NewItems& newItems, int iPass, size_t endItemsCount, bool force);

    void MergeItems(ItemOrdering& itemOrdering, const GroupItemBase& toMerge, const OrderingHint& hint, void* pComputedItemContext);
};

// When a computed or indirect item, or nameless grouping, specifies a hint and
// the subordinate does not, propagate the hint.
const OrderingHint& ChooseHint(BaseItem* delegate, const OrderingHint& hint)
{
    return !delegate || delegate->orderingHint.type == OrderingHint::Unspecified
           ? hint
           : delegate->orderingHint;
}

// "Collection" of items is the first pass of visitation, and resolves
// delegation and delayed computation and splices anonymous group nodes.
// This first pass is done at each group, starting with a top-level group.
// This pass does not descend to the leaves.  Rather, the visitation passes
// alternate as the entire tree is recursively visited.

// forward declaration for mutually recursive functions
void CollectItem(CollectedItems& collection, BaseItem* Item, const OrderingHint& hint, void* pComputedItemContext);
void CollectItems(CollectedItems& collection, const GroupItemBase& items,
                  const OrderingHint& hint, void* pComputedItemContext)
{
    for ( auto& item : items ) {
        CollectItem(collection, item.get(),
                    ChooseHint(item.get(), hint), pComputedItemContext);
    }
}

void CollectItem(CollectedItems& collection,
                 BaseItem* pItem, const OrderingHint& hint, void* pComputedItemContext)
{
    if (!pItem) {
        return;
    }

    using namespace Registry;
    if (const auto pIndirect
            =dynamic_cast<IndirectItemBase*>(pItem)) {
        auto delegate = pIndirect->ptr.get();
        if (delegate) {
            // recursion
            CollectItem(collection, delegate,
                        ChooseHint(delegate, pIndirect->orderingHint), pComputedItemContext);
        }
    } else if (const auto pComputed
                   =dynamic_cast<ComputedItemBase*>(pItem)) {
        auto result = pComputed->factory(pComputedItemContext);
        if (result) {
            // Guarantee long enough lifetime of the result
            collection.computedItems.push_back(result);
            // recursion
            CollectItem(collection, result.get(),
                        ChooseHint(result.get(), pComputed->orderingHint),
                        pComputedItemContext);
        }
    } else if (auto pGroup = dynamic_cast<GroupItemBase*>(pItem)) {
        if (pGroup->GetOrdering() == GroupItemBase::Anonymous) {
            // anonymous grouping item is transparent to path calculations
            // collect group members now
            // recursion
            CollectItems(collection, *pGroup,
                         ChooseHint(pGroup, hint), pComputedItemContext);
        } else {
            // all other group items
            // defer collection of members until collecting at next lower level
            collection.items.push_back({ pItem, nullptr, hint });
        }
    } else {
        wxASSERT(dynamic_cast<SingleItem*>(pItem));
        // common to all single items
        collection.items.push_back({ pItem, nullptr, hint });
    }
}

using Path = std::vector< Identifier >;

std::unordered_set< wxString > sBadPaths;
void BadPath(
    const TranslatableString& format, const wxString& key, const Identifier& name)
{
    // Warn, but not more than once in a session for each bad path
    auto badPath = key + '/' + name.GET();
    if (sBadPaths.insert(badPath).second) {
        auto msg = TranslatableString{ format }.Format(badPath);
        // debug message
        wxLogDebug(msg.Translation());
#ifdef IS_ALPHA
        // user-visible message
        BasicUI::ShowMessageBox(msg);
#endif
    }
}

void ReportGroupGroupCollision(const wxString& key, const Identifier& name)
{
    BadPath(
        XO("Plug-in group at %s was merged with a previously defined group"),
        key, name);
}

void ReportItemItemCollision(const wxString& key, const Identifier& name)
{
    BadPath(
        XO("Plug-in item at %s conflicts with a previously defined item and was discarded"),
        key, name);
}

void ReportConflictingPlacements(const wxString& key, const Identifier& name)
{
    BadPath(
        XO("Plug-in items at %s specify conflicting placements"),
        key, name);
}

struct ItemOrdering {
    wxString key;

    ItemOrdering(const Path& path)
    {
        // The set of path names determines only an unordered tree.
        // We want an ordering of the tree that is stable across runs.
        // The last used ordering for this node can be found in preferences at this
        // key:
        wxArrayString strings;
        for (const auto& id : path) {
            strings.push_back(id.GET());
        }
        key = '/' + ::wxJoin(strings, '/', '\0');
    }

    // Retrieve the old ordering on demand, if needed to merge something.
    bool gotOrdering = false;
    wxString strValue;
    wxArrayString ordering;

    auto Get() -> wxArrayString&
    {
        if (!gotOrdering) {
            gPrefs->Read(key, &strValue);
            ordering = ::wxSplit(strValue, ',');
            gotOrdering = true;
        }
        return ordering;
    }
};

// For each group node, this is called only in the first pass of merging of
// items.  It might fail to place an item in the first visitation of a
// registry, but then succeed in later visitations in the same or later
// runs of the program, because of persistent side-effects on the
// preferences done at the very end of the visitation.
auto CollectedItems::InsertNewItemUsingPreferences(
    ItemOrdering& itemOrdering, BaseItem* pItem)
-> bool
{
    // Note that if more than one plug-in registers items under the same
    // node, then it is not specified which plug-in is handled first,
    // the first time registration happens.  It might happen that you
    // add a plug-in, run the program, then add another, then run again;
    // registration order determined by those actions might not
    // correspond to the order of re-loading of modules in later
    // sessions.  But whatever ordering is chosen the first time some
    // plug-in is seen -- that ordering gets remembered in preferences.

    if (!pItem->name.empty()) {
        // Check saved ordering first, and rebuild that as well as is possible
        auto& ordering = itemOrdering.Get();
        auto begin2 = ordering.begin(), end2 = ordering.end(),
             found2 = std::find(begin2, end2, pItem->name);
        if (found2 != end2) {
            auto insertPoint = items.end();
            // Find the next name in the saved ordering that is known already
            // in the collection.
            while (++found2 != end2) {
                auto known = Find(*found2);
                if (known != insertPoint) {
                    insertPoint = known;
                    break;
                }
            }
            items.insert(insertPoint, { pItem, nullptr,
                                        // Hints no longer matter:
                                        {} });
            return true;
        }
    }

    return false;
}

// For each group node, this may be called in the second and later passes
// of merging of items
auto CollectedItems::InsertNewItemUsingHint(
    BaseItem* pItem, const OrderingHint& hint, size_t endItemsCount,
    bool force) -> bool
{
    auto begin = items.begin(), end = items.end(),
         insertPoint = end - endItemsCount;

    // pItem should have a name; if not, ignore the hint, and put it at the
    // default place, but only if in the final pass.
    if (pItem->name.empty()) {
        if (!force) {
            return false;
        }
    } else {
        switch (hint.type) {
        case OrderingHint::Before:
        case OrderingHint::After: {
            // Default to the end if the name is not found.
            auto found = Find(hint.name);
            if (found == end) {
                if (!force) {
                    return false;
                } else {
                    insertPoint = found;
                }
            } else {
                insertPoint = found;
                if (hint.type == OrderingHint::After) {
                    ++insertPoint;
                }
            }
            break;
        }
        case OrderingHint::Begin:
            insertPoint = begin;
            break;
        case OrderingHint::End:
            insertPoint = end;
            break;
        case OrderingHint::Unspecified:
        default:
            if (!force) {
                return false;
            }
            break;
        }
    }

    // Insert the item; the hint has been used and no longer matters
    items.insert(insertPoint, { pItem, nullptr,
                                // Hints no longer matter:
                                {} });
    return true;
}

auto CollectedItems::MergeLater(Item& found, const Identifier& name,
                                GroupItemBase::Ordering ordering) -> GroupItemBase *
{
    auto subGroup = found.mergeLater;
    if (!subGroup) {
        auto newGroup = std::make_shared<PlaceHolder>(name, ordering);
        computedItems.push_back(newGroup);
        subGroup = found.mergeLater = newGroup.get();
    }
    return subGroup;
}

void CollectedItems::SubordinateSingleItem(Item& found, BaseItem* pItem)
{
    MergeLater(found, pItem->name, GroupItemBase::Weak)->push_back(
        std::make_unique<IndirectItemBase>(
            // shared pointer with vacuous deleter
            std::shared_ptr<BaseItem>(pItem, [](void*){})));
}

void CollectedItems::SubordinateMultipleItems(Item& found, GroupItemBase& items)
{
    auto subGroup = MergeLater(found, items.name, items.GetOrdering());
    for (const auto& pItem : items) {
        subGroup->push_back(std::make_unique<IndirectItemBase>(
                                // shared pointer with vacuous deleter
                                std::shared_ptr<BaseItem>(pItem.get(), [](void*){})));
    }
}

bool CollectedItems::MergeWithExistingItem(
    ItemOrdering& itemOrdering, BaseItem* pItem)
{
    // Assume no null pointers remain after CollectItems:
    const auto& name = pItem->name;
    const auto found = Find(name);
    if (found != items.end()) {
        // Collision of names between collection and registry!
        // There are 2 * 2 = 4 cases, as each of the two are group items or
        // not.
        auto pCollectionGroup = dynamic_cast< GroupItemBase* >(found->visitNow);
        auto pRegistryGroup = dynamic_cast< GroupItemBase* >(pItem);
        if (pCollectionGroup) {
            if (pRegistryGroup) {
                // This is the expected case of collision.
                // Subordinate items from one of the groups will be merged in
                // another call to MergeItems at a lower level of path.
                // Note, however, that at most one of the two should be a
                // strongly ordered item; if not, we must lose the extra
                // information carried by one of them.
                bool pCollectionGrouping
                    =(pCollectionGroup->GetOrdering() != GroupItemBase::Strong);
                auto pRegistryGrouping
                    =(pRegistryGroup->GetOrdering() != GroupItemBase::Strong);
                if (!(pCollectionGrouping || pRegistryGrouping)) {
                    ReportGroupGroupCollision(itemOrdering.key, name);
                }

                if (pCollectionGrouping && !pRegistryGrouping) {
                    // Swap their roles
                    found->visitNow = pRegistryGroup;
                    SubordinateMultipleItems(*found, *pCollectionGroup);
                } else {
                    SubordinateMultipleItems(*found, *pRegistryGroup);
                }
            } else {
                // Registered non-group item collides with a previously defined
                // group.
                // Resolve this by subordinating the non-group item below
                // that group.
                SubordinateSingleItem(*found, pItem);
            }
        } else {
            if (pRegistryGroup) {
                // Subordinate the previously merged single item below the
                // newly merged group.
                // In case the name occurred in two different static registries,
                // the final merge is the same, no matter which is treated first.
                auto demoted = found->visitNow;
                found->visitNow = pRegistryGroup;
                SubordinateSingleItem(*found, demoted);
            } else {
                // Collision of non-group items is the worst case!
                // The later-registered item is lost.
                // Which one you lose might be unpredictable when both originate
                // from static registries.
                ReportItemItemCollision(itemOrdering.key, name);
            }
        }
        return true;
    } else {
        // A name is registered that is not known in the collection.
        return false;
    }
}

bool CollectedItems::MergeLikeNamedItems(ItemOrdering& itemOrdering,
                                         NewItems::const_iterator left, NewItems::const_iterator right,
                                         const int iPass, size_t endItemsCount, bool force)
{
    // Try to place the first item of the range.
    // If such an item is a group, then we always retain the kind of
    // grouping that was registered.  (Which doesn't always happen when
    // there is name collision in MergeWithExistingItem.)
    auto iter = left;
    auto& item = *iter;
    auto pItem = item.first;
    const auto& hint = item.second;
    bool success = false;
    if (iPass == -1) {
        // A first pass consults preferences.
        success = InsertNewItemUsingPreferences(itemOrdering, pItem);
    } else if (iPass == hint.type) {
        // Later passes for choosing placements.
        // Maybe it fails in this pass, because a placement refers to some
        // other name that has not yet been placed.
        success
            =InsertNewItemUsingHint(pItem, hint, endItemsCount, force);
        wxASSERT(!force || success);
    }

    if (success) {
        // Resolve collisions among remaining like-named items.
        ++iter;
        if (iter != right && iPass != 0
            && iter->second.type != OrderingHint::Unspecified
            && !(iter->second == hint)) {
            // A diagnostic message sometimes
            ReportConflictingPlacements(itemOrdering.key, pItem->name);
        }
        while (iter != right) {
            // Re-invoke MergeWithExistingItem for this item, which is known
            // to have a name collision, so ignore the return value.
            MergeWithExistingItem(itemOrdering, iter++->first);
        }
    }

    return success;
}

inline bool MajorComp(
    const CollectedItems::NewItem& a, const CollectedItems::NewItem& b)
{
    // Descending sort!
    return a.first->name > b.first->name;
}

inline bool MinorComp(
    const CollectedItems::NewItem& a, const CollectedItems::NewItem& b)
{
    // Sort by hint type.
    // This sorts items with unspecified hints last.
    return a.second < b.second;
}

inline bool Comp(
    const CollectedItems::NewItem& a, const CollectedItems::NewItem& b)
{
    if (MajorComp(a, b)) {
        return true;
    }
    if (MajorComp(b, a)) {
        return false;
    }
    return MinorComp(a, b);
}

void CollectedItems::MergeItemsAscendingNamesPass(ItemOrdering& itemOrdering,
                                                  NewItems& newItems, const int iPass, size_t endItemsCount, bool force)
{
    // Inner loop over ranges of like-named items.
    auto rright = newItems.rbegin();
    auto rend = newItems.rend();
    while (rright != rend) {
        // Find the range
        using namespace std::placeholders;
        auto rleft = std::find_if(
            rright + 1, rend, std::bind(MajorComp, _1, *rright));

        bool success = MergeLikeNamedItems(itemOrdering,
                                           rleft.base(), rright.base(), iPass, endItemsCount, force);

        if (success) {
            auto diff = rend - rleft;
            newItems.erase(rleft.base(), rright.base());
            rend = newItems.rend();
            rleft = rend - diff;
        }
        rright = rleft;
    }
}

void CollectedItems::MergeItemsDescendingNamesPass(ItemOrdering& itemOrdering,
                                                   NewItems& newItems, const int iPass, size_t endItemsCount, bool force)
{
    // Inner loop over ranges of like-named items.
    auto left = newItems.begin();
    while (left != newItems.end()) {
        // Find the range
        using namespace std::placeholders;
        auto right = std::find_if(
            left + 1, newItems.end(), std::bind(MajorComp, *left, _1));

        bool success = MergeLikeNamedItems(itemOrdering, left, right, iPass,
                                           endItemsCount, force);

        if (success) {
            left = newItems.erase(left, right);
        } else {
            left = right;
        }
    }
}

void CollectedItems::MergeItems(ItemOrdering& itemOrdering,
                                const GroupItemBase& toMerge, const OrderingHint& hint,
                                void* pComputedItemContext)
{
    NewItems newItems;

    {
        // First do expansion of nameless groupings, and caching of computed
        // items, just as for the previously collected items.
        CollectedItems newCollection{ {}, computedItems };
        CollectItems(newCollection, toMerge, hint, pComputedItemContext);

        // Try to merge each, resolving name collisions with items already in the
        // tree, and collecting those with names that don't collide.
        for (const auto& item : newCollection.items) {
            if (!MergeWithExistingItem(itemOrdering, item.visitNow)) {
                newItems.push_back({ item.visitNow, item.hint });
            }
        }
    }

    // Choose placements for items with NEW names.

    // First sort so that like named items are together, and for the same name,
    // items with more specific ordering hints come earlier.
    std::sort(newItems.begin(), newItems.end(), Comp);

    // Outer loop over trial passes.
    int iPass = -1;
    bool force = false;
    size_t oldSize = 0;
    size_t endItemsCount = 0;
    auto prevSize = newItems.size();
    while (!newItems.empty())
    {
        // If several items have the same hint, we try to preserve the sort by
        // name (an internal identifier, not necessarily user visible), just to
        // have some determinacy.  That requires passing one or the other way
        // over newItems.
        bool descending
            =(iPass == OrderingHint::After || iPass == OrderingHint::Begin);

        if (descending) {
            MergeItemsDescendingNamesPass(itemOrdering,
                                          newItems, iPass, endItemsCount, force);
        } else {
            MergeItemsAscendingNamesPass(itemOrdering,
                                         newItems, iPass, endItemsCount, force);
        }

        auto newSize = newItems.size();
        ++iPass;

        if (iPass == 0) {
            // Just tried insertion by preferences.  Don't try it again.
            oldSize = newSize;
        } else if (iPass == OrderingHint::Unspecified) {
            if (!force) {
                iPass = 0, oldSize = newSize;
                // Are we really ready for the final pass?
                bool progress = (oldSize > newSize);
                if (progress) {
                    // No.  While some progress is made, don't force final placements.
                    // Retry Before and After hints.
                } else {
                    force = true;
                }
            }
        } else if (iPass == OrderingHint::End && endItemsCount == 0) {
            assert(newSize >= prevSize || newSize == 0);
            // Remember the size before we put the ending items in place
            endItemsCount = newSize - prevSize;
        }

        prevSize = newSize;
    }
}

// forward declaration for mutually recursive functions
void VisitItem(
    VisitorBase& visitor, CollectedItems& collection, Path& path, const BaseItem* pItem, const GroupItemBase* pToMerge,
    const OrderingHint& hint, bool& doFlush, void* pComputedItemContext);
void VisitItems(
    VisitorBase& visitor, CollectedItems& collection,
    Path& path, const GroupItemBase& group,
    const GroupItemBase* pToMerge, const OrderingHint& hint,
    bool& doFlush, void* pComputedItemContext)
{
    // Make a NEW collection for this subtree, sharing the memo cache
    CollectedItems newCollection{ {}, collection.computedItems };

    // Gather items at this level
    // (The ordering hint is irrelevant when not merging items in)
    CollectItems(newCollection, group, {},
                 pComputedItemContext);

    path.push_back(group.name.GET());

    // Merge with the registry
    if (pToMerge) {
        ItemOrdering itemOrdering{ path };
        newCollection.MergeItems(itemOrdering, *pToMerge, hint,
                                 pComputedItemContext);

        // Remember the NEW ordering, if there was any need to use the old.
        // This makes a side effect in preferences.
        if (itemOrdering.gotOrdering) {
            wxString newValue;
            for ( const auto& item : newCollection.items ) {
                const auto& name = item.visitNow->name;
                if (!name.empty()) {
                    newValue += newValue.empty()
                                ? name.GET()
                                : ',' + name.GET();
                }
            }
            if (newValue != itemOrdering.strValue) {
                gPrefs->Write(itemOrdering.key, newValue);
                doFlush = true;
            }
        }
    }

    // Now visit them
    for ( const auto& item : newCollection.items ) {
        VisitItem(visitor, collection, path,
                  item.visitNow, item.mergeLater, item.hint,
                  doFlush, pComputedItemContext);
    }

    path.pop_back();
}

void VisitItem(
    VisitorBase& visitor, CollectedItems& collection,
    Path& path, const BaseItem* pItem,
    const GroupItemBase* pToMerge, const OrderingHint& hint,
    bool& doFlush, void* pComputedItemContext)
{
    if (!pItem) {
        return;
    }

    if (const auto pSingle
            =dynamic_cast<const SingleItem*>(pItem)) {
        wxASSERT(!pToMerge);
        visitor.Visit(*pSingle, path);
    } else if (const auto pGroup
                   =dynamic_cast<const GroupItemBase*>(pItem)) {
        visitor.BeginGroup(*pGroup, path);
        // recursion
        VisitItems(
            visitor, collection, path, *pGroup, pToMerge, hint, doFlush,
            pComputedItemContext);
        visitor.EndGroup(*pGroup, path);
    } else {
        wxASSERT(false);
    }
}
}

namespace Registry {
EmptyContext EmptyContext::Instance;

BaseItem::~BaseItem() {}

IndirectItemBase::~IndirectItemBase() {}

ComputedItemBase::~ComputedItemBase() {}

SingleItem::~SingleItem() {}

GroupItemBase::~GroupItemBase() {}
auto GroupItemBase::GetOrdering() const -> Ordering { return Strong; }

VisitorBase::~VisitorBase() = default;

void detail::Visit(VisitorBase& visitor,
                   const GroupItemBase* pTopItem,
                   const GroupItemBase* pRegistry, void* pComputedItemContext)
{
    assert(pComputedItemContext);
    std::vector< BaseItemSharedPtr > computedItems;
    bool doFlush = false;
    CollectedItems collection{ {}, computedItems };
    Path emptyPath;
    VisitItem(
        visitor, collection, emptyPath, pTopItem,
        pRegistry, pRegistry ? pRegistry->orderingHint : OrderingHint(), doFlush, pComputedItemContext);
    // Flush any writes done by MergeItems()
    if (doFlush) {
        gPrefs->Flush();
    }
}

OrderingPreferenceInitializer::OrderingPreferenceInitializer(
    Literal root, Pairs pairs)
    : mPairs{std::move(pairs)}
    , mRoot{root}
{
    (*this)();
}

void OrderingPreferenceInitializer::operator ()()
{
    bool doFlush = false;
    for (const auto& pair : mPairs) {
        const auto key = wxString{ '/' } + mRoot + pair.first;
        if (gPrefs->Read(key).empty()) {
            gPrefs->Write(key, pair.second);
            doFlush = true;
        }
    }

    if (doFlush) {
        gPrefs->Flush();
    }
}

void detail::RegisterItem(GroupItemBase& registry, const Placement& placement,
                          BaseItemPtr pItem)
{
    // Since registration determines only an unordered tree of menu items,
    // we can sort children of each node lexicographically for our convenience.
    std::vector<BaseItemPtr>* pItems{};
    struct Comparator {
        bool operator()
            (const Identifier& component, const BaseItemPtr& pItem) const
        {
            return component < pItem->name;
        }

        bool operator()
            (const BaseItemPtr& pItem, const Identifier& component) const
        {
            return pItem->name < component;
        }
    };
    auto find = [&pItems]( const Identifier& component ){
        return std::equal_range(
            pItems->begin(), pItems->end(), component, Comparator());
    };

    auto pNode = &registry;
    pItems = &pNode->items;

    const auto pathComponents = ::wxSplit(placement.path, '/');
    auto pComponent = pathComponents.begin(), end = pathComponents.end();

    // Descend the registry hierarchy, while groups matching the path components
    // can be found
    auto debugPath = wxString{ '/' } + registry.name.GET();
    while (pComponent != end) {
        const auto& pathComponent = *pComponent;

        // Try to find an item already present that is a group item with the
        // same name; we don't care which if there is more than one.
        const auto range = find(pathComponent);
        const auto iter2 = std::find_if(range.first, range.second,
                                        [](const BaseItemPtr& pItem){
            return dynamic_cast< GroupItemBase* >(pItem.get());
        });

        if (iter2 != range.second) {
            // A matching group in the registry, so descend
            pNode = static_cast< GroupItemBase* >(iter2->get());
            pItems = &pNode->items;
            debugPath += '/' + pathComponent;
            ++pComponent;
        } else {
            // Insert at this level;
            // If there are no more path components, and a name collision of
            // the added item with something already in the registry, don't resolve
            // it yet in this function, but see MergeItems().
            break;
        }
    }

    // Create path group items for remaining components
    while (pComponent != end) {
        auto newNode
            =std::make_unique<PlaceHolder>(*pComponent, GroupItemBase::Weak);
        pNode = newNode.get();
        pItems->insert(find(pNode->name).second, std::move(newNode));
        pItems = &pNode->items;
        ++pComponent;
    }

    // Remember the hint, to be used later in merging.
    pItem->orderingHint = placement.hint;

    // Now insert the item.
    pItems->insert(find(pItem->name).second, std::move(pItem));
}

template struct GroupItem<DefaultTraits>;
}
